package dict

import (
	"unsafe"
)

// iterator 实现了一个对字典的迭代器。
// 不过考虑到我们将为字典提供 `Range` 方法，故该迭代器就不往外暴露了。
type iterator struct {
	d                  *Dict
	tableIndex         int
	safe               bool
	fingerprint        int64
	entry              *entry
	bucketIndex        uint64
	waitFirstIteration bool
}

func newIterator(d *Dict, safe bool) *iterator {
	return &iterator{
		d:                  d,
		safe:               safe,
		waitFirstIteration: true,
	}
}

// next 会依次扫描字典中哈希表的所有 buckets，并将其中的 entry 一一返回。
// 如果字典正在 rehash，那么会在扫描完哈希表 1 后，继续扫描哈希表 2。需要
// 注意的是，如果在迭代期间，继续向字典中添加数据可能没法被扫描到！
func (it *iterator) next() *entry {
	for {
		if it.entry == nil {
			if it.waitFirstIteration {
				// 第一次迭代，要做点特别的事情~
				if it.safe {
					// 告诉 dict，有正在运行的安全迭代器，进而阻止某些操作时的 rehash 操作
					it.d.iterators++
				} else {
					it.fingerprint = it.d.fingerprint()
				}
				it.waitFirstIteration = false
			}

			ht := it.d.hashTables[it.tableIndex]
			if it.bucketIndex >= ht.size {
				if !it.d.isRehashing() || it.tableIndex != 0 {
					return nil
				}

				// 切换到第二个哈希表继续扫描
				it.tableIndex = 1
				it.bucketIndex = 0
				ht = it.d.hashTables[1]
			}

			it.entry = ht.buckets[it.bucketIndex]
			it.bucketIndex++
		} else {
			it.entry = it.entry.next
		}

		if it.entry != nil {
			return it.entry
		}
	}
}

func (it *iterator) release() {
	if it.safe {
		it.d.iterators--
	} else {
		fp := it.d.fingerprint()
		if fp != it.fingerprint {
			panic("operations like 'LoadOrStore', 'Load' or 'Delete' are not safe for an unsafe iterator")
		}
	}
}

func (d *Dict) rangeDict(fn func(key, value interface{}) bool, safe bool) {
	it := newIterator(d, safe)
	defer it.release()

	for {
		if ent := it.next(); ent != nil {
			if !fn(ent.key, ent.value) {
				break
			}
		} else {
			break
		}
	}
}

// fingerprint 计算出字典指纹，相当于给字典某刻状态盖个戳。
// 在非安全模式下使用迭代器时，原则上是不允许执行查找、插入和删除
// 操作的，否则可能引起 rehash，导致迭代结果可能会重复扫描到某
// 些 keys；所以这里会在迭代结束后再次计算下字典状态，保证前后
// 指纹相等，否则需要告知用户进行了不当的操作~
// 算法参考 redis/src/dict.c#dictFingerprint
func (d *Dict) fingerprint() int64 {
	metas := []int64{
		// meta of table 0
		int64(uintptr(unsafe.Pointer(&d.hashTables[0].buckets))),
		int64(d.hashTables[0].size),
		int64(d.hashTables[0].used),
		// meta of table 1
		int64(uintptr(unsafe.Pointer(&d.hashTables[1].buckets))),
		int64(d.hashTables[1].size),
		int64(d.hashTables[1].used),
	}

	var hash int64
	for _, meta := range metas {
		hash += meta
		// 使用 Tomas Wang 64 位整数 hash 算法
		hash = (hash << 21) - hash - 1
		hash = hash ^ (hash >> 24)
		hash = (hash + (hash << 3)) + (hash << 8) // hash * 256
		hash = hash ^ (hash >> 14)
		hash = (hash + (hash << 2)) + (hash << 4) // hash * 21
		hash = hash ^ (hash >> 28)
		hash = hash + (hash << 31)
	}

	return hash
}
